package pers.qianyu.month_202012.date_20201225.dp_bag;

/**
 * 801. 背包问题X
 * https://www.lintcode.com/problem/backpack-x/description
 *
 * @author mizzle rain
 * @date 2020-12-25 20:05
 */
public class BackPackX {
    /**
     * @param n: the money you have
     * @return: the minimum money you have to give
     */
    public int backPackX(int n) {
        int[] prices = {150, 250, 350};
        int[] dp = new int[n + 1];
        for (int price : prices) {
            for (int i = price; i <= n; i++) {
                dp[i] = Math.max(dp[i], dp[i - price] + price);
            }
        }
        return n - dp[n];
    }
}
